#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<string>
#include<string.h>
#include<time.h>
#include<ctype.h>
#include<sys/time.h>
#include <map>

using namespace std;

/* Tamanho máximo de uma palavra -> 5 letras + '\0' */
#define TAM_PALAVRA 6

/* Estrutura para armazenar as palavras */
map<string, bool> palavras;

/* Função para calcular o tempo de execução */
double tempo(){
  struct timeval tv;
  gettimeofday(&tv,0);
  return tv.tv_sec + tv.tv_usec/1e6;
}

/* Quebra as palavras e as insere na estrutura */
void insert(string palavra_grande){
  int i, tamanhoPalavra = palavra_grande.size(); 
  int qte_pedacos = ceil(((float)tamanhoPalavra) / (TAM_PALAVRA - 1)); 
  int size = ceil(((float)tamanhoPalavra) / qte_pedacos);
  string palavra;
  for(i = 0; i < tamanhoPalavra; i+=size){
     palavra = palavra_grande.substr(i, size);
     palavras[palavra] = true;
   }
}

/* Função que carrega o vetor de palavras do arquivo, salvando as palavras no vetor de palavras. Ao final ela retorna a quantidade de palavras da estrutura */
int carregaPalavras(FILE *fp){
  int i, tamanhoPalavra, qteNaoLetras;
  char buffer[50];
  string palavra;
  
  while (fscanf( fp, "%[^ ,\n\r]s", buffer) != EOF){
    tamanhoPalavra = strlen(buffer);
    
    /* Apenas considera palavras entre 2 e 20 letras */
    if(tamanhoPalavra > 1 && tamanhoPalavra < 20){
      
      /* Remove caracteres que não são letras e passa a palavra lida para minúsculo */
      qteNaoLetras = 0;
      for (i = 0; i < tamanhoPalavra; i++){
	if(!isalpha(buffer[i])){
	  qteNaoLetras++;
	  continue;
	}
	buffer[i-qteNaoLetras] = tolower(buffer[i]);
      }
      buffer[i-qteNaoLetras] = '\0';
      if(tamanhoPalavra - qteNaoLetras <= 1) continue;

      /* Insere a palavra no vetor, quebrando-a se for grande */
      palavra = buffer;
      insert(palavra);
    }
    /* Pula o caracter inválido */
    fgetc(fp); 
  } 
  return palavras.size();
}

/* Função que gera a palavra */
void gera_palavra(char* palavra){
  int i, tamanho;
  
  /* Sorteia um número para ser o tamanho da palavra a ser gerada (de 2 a 5 letras) */
  tamanho = (rand()%(TAM_PALAVRA-2)) + 2;
    
  /* Gera cada letra da palavra individualmente */
  for(i = 0; i < tamanho; i++){
    palavra[i] = (rand()%26) + 'a';  
  }
  /* Termina a palavra, colocando '\0' no final */
  palavra[i] = '\0';
}

/* Calcula o percentual de palavras encontradas */
float calculaPercentual(int achadas, int total){
  return (((float) achadas) / ((float) total));
}

int main(void){
  int numPalavras, numAchadas = 0;
  float faixa_percentual = 0.1;
  char buffer[TAM_PALAVRA];
  
  /* Iterador do map */
  map<string, bool>::iterator it;
  string palavra;
  
  /* Variáveis para registrar o tempo de início e término de execução */
  double start, end;
  
  /* ==================================================================================================*/
  /* Inicializa e carrega a lista de palavras, registrando o tempo disso */
  FILE *fp;
  fp = fopen("palavras.txt", "r");
  if(fp < 0){
    printf("Não foi possivel abrir o arquivo de palavras\n");
    return -1;
  }
  start = tempo();
  numPalavras = carregaPalavras(fp);
  end = tempo();
  printf("=====================================\n");
  printf("Tempo carregando as palavras e removendo as repetidas = %f segundos\n", end-start);
  printf("Quantidade de palavras lidas = %d\n", numPalavras);
  /* ==================================================================================================*/
  
  /* ==================================================================================================*/
  /* Agora começa a gerar as palavras */
  /* Registra tempo de início */
  start = tempo();
      
  /* Semeia a palavra */
  srand(time(NULL));
  do{
    /* Gera a palavra */
    gera_palavra(buffer);
    
    /* Procura a palavra gerada na lista de palavras */
    palavra = buffer;
    it = palavras.find(palavra);
    if (it != palavras.end()){  /* Se achar... */
      palavras.erase(it);
      numAchadas++;
      
      /* Verifica se passou de uma faixa percentual (10%, 20%, ...) */
      if(calculaPercentual(numAchadas, numPalavras) > faixa_percentual){
	end = tempo();
	printf("Foram encontradas %d porcento das palavras em %.2f segundos\n", (int)(100.0 * faixa_percentual), end-start);
	faixa_percentual += 0.1;
      }
    }
  } while(numAchadas < numPalavras);

  /* Registra tempo de fim */
  end = tempo();
  /* ==================================================================================================*/    
    
  /* Exibe os resultado */
  printf("-------------------------------------\n");
  printf("Tempo de execucao na geracao de palavras = %f segundos\n", end-start);
  printf("Quantidade de palavras encontradas = %d porcento\n", (int)(100.0 * calculaPercentual(numAchadas, numPalavras)));
  printf("=====================================\n");
  return 0;  
}

